package com.vint.leetcode;

import com.vint.common.TreeNode;

/*
 *
 */
public class Leetcode654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return cons(nums,0,nums.length-1);
    }

    public TreeNode cons(int[] nums, int left, int right){
        if(left>right){
            return null;
        }
        if(left == right){
            return new TreeNode(nums[left]);
        }

        int maxIndex=left;
        int maxValue = Integer.MIN_VALUE;
        //这里题目保证了只出现一个最大值，即所有值不同
        for(int i=left; i<=right; i++){
            if(nums[i]> maxValue){
                maxIndex = i;
                maxValue = nums[i];
            }
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = cons(nums,left,maxIndex-1);
        root.right = cons(nums,maxIndex+1,right);
        return root;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,1,6,0,5};
        Leetcode654 leetcode654 = new Leetcode654();
        TreeNode root = leetcode654.constructMaximumBinaryTree(nums);
        System.out.println("success");
    }
  }
